#pragma once
#include<iostream>
using namespace std;
namespace GIS20178
{
#define maxsize 30
	typedef char datatype;
	typedef int weighttype;
	typedef struct htnode {
		datatype data;
		weighttype weight;
		int parent, lchild, rchild;
	};

	typedef struct hftree {
		htnode elem[maxsize];
		int num, root;
	};

#define maxweight 1000
	void createhftree(hftree& ht, datatype value[], weighttype fr[], int n)
	{
		int i, j, k, s1, s2;
		weighttype min1, min2;
		for (i = 0; i < n; i++)
		{
			ht.elem[i].data = value[i];
			ht.elem[i].weight = fr[i];
		}
		for (i = 0; i < 2 * n - 1; i++)
		{
			ht.elem[i].parent = ht.elem[i].lchild = ht.elem[i].rchild = -1;
		}

		for (i = n; i < 2 * n - 1; i++)
		{
			min1 = min2 = maxweight;
			s1 = s2 = 0;
			for (k = 0; k < 1; k++)
			{
				if (ht.elem[k].parent == -1) 
				{
					if (ht.elem[k].weight < min1)
					{
						min2 = min1;
						min1 = ht.elem[k].weight;
						s2 = s1;
						s1 = k;
					}
					else if (ht.elem[k].weight < min2)
					{
						min2 = ht.elem[k].weight;
						s2 = k;
					}
				}
			}
			ht.elem[s1].parent = ht.elem[s2].parent = i;
			ht.elem[i].lchild = s1;
			ht.elem[i].rchild = s2;
			ht.elem[i].weight = ht.elem[s1].weight + ht.elem[s2].weight;
		}
		ht.num = n;
		ht.root=2*n-2;
	}


}